package algorithm;

/**
 * 手写实现LRU
 * LRU，距离现在最早使用的会被我们替换掉，一种淘汰机制
 * 1. 当数组未满的情况下，随便插
 * 2. 数组满了之后，插入介于头和尾的元素，需要记录其之前存在的下标，然后将大于该下标的元素整体前移。
 * 3. 数组满了之后，插入最新的元素等于什么操作也没有。保持原样
 * 3. 数组满了之后，插入一个不存在的元素 等同于 插入数组最开始的元素。
 * 比如 1、2、3、4 之后插入5 和 1、2、3、4 之后插入1 结果分别为 2、3、4、5和 2、3、4、1。
 * 原则：
 * 最新的在最后
 */
public class HandMakeCacheLRU {
    //添加次数计数器
    static int count = 10;

    //数组元素计数器
    static int size = 0;

    //最大长度
    int maxSize;

    //对象数组
    int[] listArray;


    //顺序表的初始化
    public HandMakeCacheLRU(int maxSize){
        listArray = new int[maxSize];
        this.maxSize =  maxSize;
    }

    public int getSize() {
        return size;
    }

    public void insert(int obj) {
        // 插入过程不应该指定下标，对于用户来讲这应该是透明的，只需要暴露插入的顺序
        boolean exist = false; //每次insert校验一下是否存在
        int location = 0;//对于已有元素记录存在的位置
        for(int i=0; i<maxSize; i++){
            if(obj == listArray[i]) {
                exist = true;
                location = i;
            }
        }
        //当前情况小于缓存大小
        if(size < this.maxSize){
            if(exist){//元素已经存在,有变化
                //移动
                if (location == 0 ){
                    moveArrayElements(listArray,0,size-2);
                } else if (location < size - 1) { // 已存在元素不在最新的位置
                    moveArrayElements(listArray,location,size-2);
                }
                //重写
                listArray[size - 1] = obj; // 由于已存在
            } else {//元素不存在
                listArray[size] = obj;
                size++;
            }
        } else {
            // 此时缓存为满，这时候要保留最末端元素先
            if (!exist || obj == listArray[0]) { // 新元素添加进来，和最远元素添加进来效果一样
                moveArrayElements(listArray,0,maxSize-2);
            } else if (obj != listArray[maxSize - 1]) {
                moveArrayElements(listArray,location,maxSize-2);
            } // 如果添加的是上次添加的元素，则不管了。。
            listArray[maxSize - 1] = obj;
        }
        count++; // 计数
    }

    public Object get(int index){
        return listArray[index];
    }

    /**
     * 平移数组的方法，start是要移动至头的位置,end为最后被移动的位置
     * @param arr
     * @param start
     * @param end
     */
    public void moveArrayElements(int[] arr, int start ,int end){
        for(int i=start;i<=end;i++){
            arr[i] = arr[i+1];
        }
    }

    public static void main(String[] args) {
        int cacheSize = 5;
        HandMakeCacheLRU list = new HandMakeCacheLRU(cacheSize);
        try
        {
            list.insert(1);
            list.insert(2);
            list.insert(3);
            list.insert(1);
            list.insert(3);
            list.insert(4);
            list.insert(4);
            list.insert(5);
            list.insert(6);

            for(int i=0;i<cacheSize;i++)
            {
                System.out.println(list.get(i));
            }
            System.out.println("成功插入"+count+"次元素.");

        }
        catch(Exception ex)
        {
            ex.printStackTrace();
        }
    }

}
